# -*- coding: utf-8 -*-

"""剑指 Offer II 040. 矩阵中最大的矩形
给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。
注意：此题 matrix 输入格式为一维 01 字符串数组。

示例 1：
输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。

示例 2：
输入：matrix = []
输出：0

示例 3：
输入：matrix = ["0"]
输出：0

示例 4：
输入：matrix = ["1"]
输出：1

示例 5：
输入：matrix = ["00"]
输出：0

提示：
rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'"""


class Solution:
    """本题需要有一个观念的转变，按通常考虑，选定一个点为左上角顶点，寻找其右下区域可勾勒的最大矩形，那么怎么来描述一个矩形？在此遇到困难。
    换条路，凑矩形。先用单调栈取得每个‘1’可以向后延展的最大距离，再遍历所有点，对于每个点，向下凑矩形，每添加一行，可以凑的矩形都不一样，得到的面积也不一样
    ，凑到不能凑为止，就可以得到以该点为左上角能勾勒的最大矩形。
    
    虽然提交成功，但是效率比较低，看题解，有妙招：
    对每一行取直方图，对该直方图计算最大矩形面积（39题），对比每行直方图最大面积得结果。
    
    这道题提交成功给了我极大的鼓励，虽然没有想到直方图的妙招，但是换了一个角度，从勾勒矩形到拼凑矩形，最终解题。"""
    def maximalRectangle(self, matrix) -> int:
        rightl = [[0 for _ in matrix[0]] for _ in matrix]
        for row, arr in zip(range(len(matrix)), matrix):
            stack = []
            for col in range(len(arr)):
                while stack and arr[stack[-1]] == '1' and arr[col] == '0':
                    last = stack.pop()
                    rightl[row][last] = col-last
                if arr[col] == '1':
                    stack.append(col)
            col += 1
            while stack and arr[stack[-1]] == '1':
                last = stack.pop()
                rightl[row][last] = col-last
        
        max_rect = 0
        bottom = len(rightl)
        for row, arr in zip(range(bottom), rightl):
            for col in range(len(arr)):
                down, min_rightl, height = row, arr[col], 0
                while down < bottom and rightl[down][col] > 0:
                    height += 1
                    min_rightl = min(min_rightl, rightl[down][col])
                    max_rect = max(max_rect, height*min_rightl)
                    down += 1
        return max_rect


if __name__ == '__main__':
    so = Solution()
    print(so.maximalRectangle(["10100","10111","11111","10010"]))

